package com.ayuer.chapter05;

/**
 * 基于无序数组实现优先级队列
 */
public class PriorityQueue<E> implements Queue<E> {

    class PriorityNode<E> {
        int priority;
        E element;
    }

    private PriorityNode<E>[] array;

    private int size;

    private final int capacity;

    public PriorityQueue(int capacity) {
        this.capacity = capacity;
        array = (PriorityNode<E>[]) new PriorityNode[capacity];
    }

    @Override
    public boolean offer(E e) {
        if (isEmpty()) {
            return false;
        }
        //入队
        array[size++] = new PriorityNode<>();
        return true;
    }


    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        int max = selectMax();
        PriorityNode<E> tmp = new PriorityNode<>();
        array[max] = tmp;
        //移动数组
        for (int i = max; i < array.length; i++) {
            array[i] = array[i + 1];
        }
        array[size--] = null; //进行释放
        return tmp.element;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[selectMax()].element;
    }

    @Override
    public boolean isEmpty() {
        return size == capacity;
    }

    @Override
    public boolean isFull() {
        return false;
    }

    public int selectMax() {
        int max = -1;
        for (int i = 0; i < array.length; i++) {
            if (array[i].priority > max) {
                max = array[i].priority;
            }
        }
        return max;
    }
}
